1. Field of the Invention
The invention in general relates to error detection in radio frequency (RF) communication devices, and more particularly to a block code error detection and correction device and method particularly suitable for use in a radio frequency identification (RFID) system.
2. Statement of the Problem
There are many different situations in which it is useful to be able to identify objects. For example, individual products or cartons of products are usually identified in stores or warehouses for inventory, sales, or other purposes. Or suitcases and packages in transit may be temporarily identified. In the past identification has been by printing or writing identification labels on the individual objects. Recently bar codes that can be automatically read by optical scanners have largely replaced other types of labeling. Now, a small, inexpensive electronic identification device, called a radio frequency identification (RFID) tag has been developed. An RFID tag is an integrated circuit chip having a simple processor and memory, an RF circuit, and a power source, usually a battery. The memory can be programmed to hold identification information. When a remote device, generally referred to as an interrogator, broadcasts a request for identification, the RFID tag responds with its stored information. Such an RFID system permits inventories to be automatically performed electronically, permits objects to be identified with more security, and has many other advantages. See for example, U.S. patent application Ser. No. 899,777.
In RFID systems it is important that the information broadcast by the interrogator and received by the RFID tag, and vice versa, be as error free as possible. Since the RFID systems may be used in areas where radio frequency interference may be common, it is important that error detection and correction devices be incorporated into the electronics of both the interrogator and the RFID tag. The present invention relates to error detection and correction apparatus and methods particularly useful in the RFID forward link. That is, the link between the interrogator and the RFID tag, as distinguished from the return link between the tag and the interrogator.
It is well-known to detect and correct errors in digital communications, and in particular RF communications, using mathematical codes. One common mathematical theory which is useful in developing error detection and correction codes is the theory of Galois fields. The mathematics discussed herein, including the mathematical operations +, -, :, etc., will be Galois field mathematics unless otherwise indicated. Symbols in bold are Galois field vectors or matrices. Typically, a code developed using Galois field theory will add additional bits to an information signal, which additional bits can be used to determine if errors occurred, and, in some cases, what the errors were. One well-known type of code developed from Galois field theory and used in error detection and correction systems is block code. Block code is a code in which the input data stream is divided into blocks of k bits, where k is an integer, and each block of k bits is mapped, one-to-one, onto a block of n bits, where n is an integer greater than k. There are then n-k redundant bits which are used to detect and correct errors. In a k bit block of binary bits there are 2.sup.k possible different signals, which we shall refer to as k-tuples, and in an n bit block there are 2.sup.n different signals, which we shall refer to as n-tuples. The code C is defined by the mapping of each k-tuple into a distinct n-tuple. If C.sup.i is an n-tuple, called a codeword, that corresponds to the ith information k-tuple, then the set of codewords C=[C.sup.1, C.sup.2, . . . C.sup.k ] defines the code C. An important parameter relating any two binary n-tuples x and y is the Hamming distance, d(x,y). The Hamming distance is the number of places in which the two binary n-tuples differ. The minimum distance, d.sub.c, of a code C, is the Hamming distance of the pair of code words in the code having the smallest Hamming distance, or in other words, the smallest number of places in which any two codewords differ. The minimum distance, d.sub.c, is an important parameter in error correction because when an error occurs, it changes one or more of the places in the original signal, and the larger the minimum distance is in a code, the more likely it is that an error can be corrected. A block code is generally identified by the parameters (k, n, d.sub.c); thus (2, 5, 3) block code is a block code that translates a 2-bit information vector into a 5-bit codeword and has a minimum distance of 3.
A systematic block code is one in which each code word, C.sup.i, contains the k information bits unmodified. The remaining n-k bits are called the parity bits. There are 2.sup.k codewords in a Code C. Since there are 2.sup.k distinct n-tuples, or codewords, in a code C, C can be seen as a subspace of dimension k in an n-dimensional space that includes all the possible 2.sup.k n-tuples.
In block code theory it is possible to describe the code C in terms of a generator matrix G such that C.sup.i =I.sub.i G where I.sub.i, the ith information word, is a k-tuple of information bits to be encoded and C.sup.i is the corresponding n-tuple codeword. For systematic block codes the matrix G can be written as G=[I:P] where I is the identity matrix, and P is called the parity check matrix.
It is also possible to define a matrix C.sup..perp. that is an orthogonal complement to C. C.sup..perp. is a subspace of dimension n-k, and any n-k linearly independent vectors that are orthogonal to C provide a set of basis vectors for this subspace. H is defined as an matrix having these basis vectors as rows. This matrix H is orthogonal to all codewords C.sup.i, that is C.sup.i H.sup.t =0, where H.sup.t denotes the transpose of the matrix H obtained by interchanging rows to obtain columns in H. For linear systematic block codes, H=[-P:I]. This provides a way of checking if a received word, v, is a codeword. Thus H is called the parity check matrix of the code. It is an n-k by n matrix.
The theory of linear block codes defines the syndrome, S of a received word, v, as S=vH.sup.t. If v is expressed as a codeword plus an error, i.e., v=C+e, where C is a codeword and e is an error pattern, then S=vH.sup.t =(C+e)H.sup.t =eH.sup.t, which shows that the syndrome, S, is completely dependent on the error pattern. This allows a vector, called a coset leader, l, to be defined which is the error associated with the syndrome, S. Since S is related to v through a matrix product with the parity check matrix H.sup.t, by tabulating all the coset leaders and their corresponding syndromes, a table can be created from which for any received word v the error can be found, providing the error is detectable. This permits the decoding of a received signal as follows. Given a received word v, compute the syndrome and look up its coset leader. If the syndrome corresponds to a correctable error, subtract the coset leader from v, to correct the error. If the syndrome corresponds to an uncorrectable error, then output a signal indicating that an error has occurred which is not correctable.
Applying the above known theory to RFID systems, because the interrogator can be connected to a standard AC power source, or will be significantly larger than the RFID tag and thus have larger batteries, the RFID forward data link generally operates at relatively high power compared to the return link, and thus will have a relatively high signal-to-noise ratio. Thus errors will ordinarily be limited to one or two bits in a typical information block. Thus the error detection system needs only to be capable of detecting and/or correcting two error bits in the typical block transmitted. Higher capabilities would be wasteful.
Although the error detection capability can be relatively low, it is important that the density of information transmitted be relatively high. That is, every error detection system adds extra bits to the data transmitted. These extra bits make each transmission longer. A typical prior art error detection scheme used in simple RF communication devices is (4, 8, 4) block code. This block code adds four extra bits for every four data bits transmitted. These extra bits require that the receiver in the RFID tag be twice as long as is necessary to receive the information bits. If a code could be found that provided the same error detection capability with fewer added bits, then the use of power in the RFID tag could be reduced, giving it longer life, and/or allowing it to have a smaller battery and thus be less expensive to manufacture.
In an electronic decoding device, the logic equations discussed above which relate the syndrome to the parity check matrix and which find the corrected signal from the received signal, are implemented in digital logic electronic components. It is desirable that the electronic logic circuit required to implement these functions be as simple as possible in order that the circuits be small and inexpensive.
For the RFID forward link, this is particularly important for the decoding components, since there is only limited space available for a circuit in the RFID tag, and since many tags are used in an RFID system, the individual tag must be inexpensive to keep the cost of the total system low. Thus there is a need for an RFID forward link that utilizes a block code that has a relatively small number of parity bits for a given error correction capability, and which is implement-able with a relatively small number of inexpensive electronic components.
3. Solution to the Problem
The invention solves the above problems by providing an electronic error correction system which utilizes (8, 13, 4) block code. The (8, 13, 4) block code adds five extra bits for every eight data bits transmitted. Compared to the prior art (4, 8, 4) block code, which adds four extra bits for every four data bits transmitted, the (8, 13, 4) block code uses 19% less bits for the same error correction capability.
The (8, 13, 4) block code is capable of correcting one bad bit in each thirteen-bit block. Further, it can always detect two bad bits per thirteen-bit block. Thus it is capable of detecting virtually every error in an RFID forward link, and can correct most errors without requiring repeated transmissions.
The invention also provides a unique parity matrix for implementing the (8, 13, 4) block code which results in a simple encoder and decoder.
The invention further provides a very simple error detection circuit that is implemented in a minimum number of logic elements.